package com.example.demo.leetcode;

import org.junit.Test;

/**
 * 接雨水，和11题有点相似，困难
 */
public class leetcode042 {

    @Test
    public void test() {
        int[] heights = new int[]{2, 1, 3, 1, 2};
        int res = trap(heights);
        System.out.println(res);
    }

    // 接雨水，四个指针，两个表示下标，两个记左右最大高度
    public int trap(int[] height) {
        int max = 0, leftMaxH = 0, rightMaxH = 0;

        int left = 0;
        int right = height.length - 1;

        while (left <= right) {
            if (leftMaxH <= rightMaxH) {
                leftMaxH = Math.max(leftMaxH, height[left]);
                max = max + (leftMaxH - height[left]);
                left++;
            } else {
                rightMaxH = Math.max(rightMaxH, height[right]);
                max = max + (rightMaxH - height[right]);
                right--;
            }
        }
        return max;
    }
}
